#include <iostream>
#define MAX_SITUATION_NUMBER 8
using namespace std;

bool check_safe(int location)
{
    //location: 羊，狼，白菜
    //羊不能和白菜在一起
    if(location & 4 == location & 1)
    {
        return false;
    }

    //羊不能和狼在一起
    if(location & 4 == location & 2)
    {
        return false;
    }

    //剩下的情况是可以的

    return true;
}

typedef struct Node
{
    int location;
    struct Node *top;
    struct Node *rear;
} Node,*Queue;

void Init(Queue L)
{
    L->rear = L;
    L->top = L;
}

int Remove(Node *p)
{
    p->top->rear = p->rear;
    p->rear->top = p->top;
    int location = p->location;
    free(p);
    return location;
}

void Append(Queue &L, int newLocation)
{
    Node *p = (Node *)malloc(sizeof(Node));
    p->location = newLocation;
    p->top = L->top;
    p->rear = L;
    L->top->rear = p;
    L->top = p;
}

void InQueue(Queue &Q, int newLocation)
{
    Append(Q, newLocation);
}

int OutQueue(Queue &Q)
{
    return Remove(Q->rear);
}

int Empty(Queue &Q)
{
    if (Q->rear == Q && Q->top == Q)
    {
        return 1;
    }
    return 0;
}

int main()
{
    int location, newLocation, count = 0;
    int route[MAX_SITUATION_NUMBER];
    Queue bfs;
    Init(bfs);
    InQueue(bfs, 000); //从三种动物都在一边开始
    while(!Empty(bfs) && count < MAX_SITUATION_NUMBER)
    {
        location = OutQueue(bfs);
        for (int target = 1; target <= 4; target <<= 1) //三种动物分别进行
        {
            newLocation = location ^ target;
        }
    }
}